package com.leetcode.leetcode3;

import java.util.HashMap;

/**
 * 和为 K 的子数组
 *
 * @author luhd
 * @date 2023-08-09
 */
public class Practice560 {
    /**
     * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
     * 输入：nums = [1,1,1], k = 2
     * 输出：2
     */
    public static void main(String[] args) {
        // int[] nums = {1, 1, 1};
        // int k = 2;
        int[] nums = {-1, -1, 1};
        int k = 0;
        System.out.println(subarraySum(nums, k));
    }

    public static int subarraySum(int[] nums, int k) {
        /*int count = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j >=0; j--) {
                sum += nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;*/
        int count = 0, pre = 0;
        HashMap<Integer, Integer> mp = new HashMap<>();
        mp.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];
            if (mp.containsKey(pre - k)) {
                count += mp.get(pre - k);
            }
            mp.put(pre, mp.getOrDefault(pre, 0) + 1);
        }
        return count;
    }
}